package Hot100;

/**
 * @author zhangmin
 * @create 2022-01-02 17:02
 */
public class maximalSquare221 {

    /**
     * 221. 最大正方形
     * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
     * dp[i][j]表示以 (i, j)(i,j) 为右下角，且只包含 11 的正方形的边长最大值。
     * dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
     * */
    public int maximalSquare(char[][] matrix) {
        int maxside=0;
        if (matrix==null||matrix.length==0||matrix[0].length==0) return maxside;
        int m=matrix.length,n=matrix[0].length;
        int[][] dp=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]=='1'){
                    if (i==0||j==0){
                        dp[i][j]=1;
                    }else {
                        dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                    }
                    maxside=Math.max(maxside,dp[i][j]);
                }
            }
        }
        return maxside*maxside;
    }
}
